package DMSXL._2024.BinaryTrees;

public class buildTree {
    public static void main(String[] args) {

    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return bulid(inorder,0, inorder.length,postorder , 0, postorder.length);
    }
    public TreeNode bulid(int[] inorder,int inBegin, int inEnd,  int[] postorder, int postBegin, int postEnd){
        if(inBegin >= inEnd || postBegin >= postEnd){
            return null;
        }
        int rootIndex = find(inorder,postorder[postEnd - 1]);
        TreeNode root = new TreeNode(inorder[rootIndex]);
        int lenOfLeft = rootIndex - inBegin;
        root.left = bulid(inorder,inBegin,rootIndex,postorder,postBegin,postBegin + lenOfLeft);
        root.right = bulid(inorder,rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1);

        return root;
    }
    //从inorder中找到位置
    public int find(int[] inorder, int value){
        for (int i = 0; i < inorder.length; i++) {
            if(value == inorder[i]){
                return i;
            }
        }
        return 0;
    }
}
